Symbols such as handwriting, when traced on electronic tablets, are typically represented by sequences of x-y coordinate pairs. A fundamental unit of handwriting is the stroke wherein a stroke can be considered as a sequence of points, represented by their respective x-y coordinates, which are generated between a tablet pen-down and pen-up motion of the writer. Characters and symbols are collections or sets of such strokes.
In a character identification system a first processing step is known as segmentation. Segmentation involves pre-processing, prior to processing by the character recognizer, the stroke input data to partition the strokes of a character, a symbol or possibly a word.
Various prior art handwritten segmentation method and apparatus are described in the following documents. In Herbst U.S. Pat. No. 4,024,500, May 17, 1977, disclose a segmentation method and apparatus which utilizes a determination of stylus velocity and three precise zones within which characters are analyzed. In Fujisawa U.S. Pat. No. 4,654,873, Mar. 31, 1987 disclose a pattern segmenter and analyzer that utilizes a number of hypothetical unit patterns (Col. 2, lines 5-8). At Col. 5, line 61 to Col. 6, line 36 there is described in relation to FIG. 9 a segmentation process and recognition process. Step 703 is said to show that a hypothetical boundary of characters is established based on information in an element attribute list 714 and a form dictionary 950. In Kuzunuki U.S. Pat. No. 4,680,804, July 14, 1987, disclose a method of designating either a character or a graphics recognition mode. In Shojima U.S. Pat. No. 4,718,103, Jan. 5, 1988, disclose a handwritten pattern recognition system that employs an angular variation between adjacent segments of a handwritten pattern and a dictionary having candidate patterns.
In Yoshida U.S. Pat. 4,764,972, Aug. 16, 1988, disclose a recognition system that employs a first memory for storing isolated characters and a second memory for storing interstroke character information. In U.S. Pat. No. 4,805,225, Feb. 14, 1989, D. Clark discloses a general purpose pattern recognition method and apparatus that includes learning and recognition modes and which is constructed of a plurality of basic feature recognizers.
In commonly assigned Fox U.S. Pat. No. 4,727,588, Feb. 23, 1988, disclose an electronic tablet and an all-points-addressable display to create handwritten images of documents which may be easily edited and subsequently stored within an information processing system.
In commonly assigned U.S. Pat. No. 4,731,857, Mar. 15, 1988, C. C. Tappert discloses a method that involves determining possible segmentation points of handwritten characters and passing all combinations of segments which may be a character to a character recognizer (Col. 3, lines 47-68). In relation to a Multi-Sort subroutine of FIG. 4 Tappert states that dictionary look-up and syntactic and semantic processing may be used to eliminate letterchain choices for which no valid word exists (col. 6, lines 45 et seq.). However, the type of syntatic and semantic processing envisioned by Tappert is a computationally expensive process that operates over all input strokes which, for even a relatively simple word, can be a potentially large number of stroke combinations. As such, this process of Tappert may not be suitable for real time character recognition if additional processing such as dictionary look-up is employed. Also, Tappert does not disclose the provision of selectable or switchable syntactic or semantic processing elements.
It is therefor an object of the invention to provide method and apparatus for providing constraint-driven recognition of on-line handwritten characters and symbols.
It is another object of the invention to provide method and apparatus to realize an efficient mechanism for constraint driven recognition as a combination of a stack algorithm and a series of cascaded filters, wherein each of the filters corresponds to one constraint.
It is another object of the invention to provide method and apparatus for providing an application program writer with a capability to dynamically activate and inactivate constraints applied to a character recognition task, thereby facilitating the processing of form applications.
It is a further object of the invention to provide methods to represent constraints in a form which provides an efficient method to verify constraints during character recognition.